#include "LinkTree.h"
#include "DoubleLinkList.h"
struct TreeNode
{
    TreeElementType data;
    struct TreeNode *parent;
    DLlist childs;
};

struct LinkTree
{
    TNode *root;
};

TNode *CreateTreeNode(TreeElementType element)
{
    TNode *newNode = (TNode*)malloc(sizeof(TNode));
    if(newNode == NULL)
    {
        printf("malloc error!\n");
        return NULL;
    }
    newNode->data = element;
    newNode->parent = NULL;
    InitDLlist(&newNode->childs);
    return newNode;
}

void FreeTreeNode(void *n)
{
    TNode *freeNode = (TNode*)n;
    if(freeNode == NULL)
        return;
    ClearDLlist(&freeNode->childs,FreeTreeNode);
    free(freeNode);
}

void *GetTreeNodeData(TNode *node)
{
    return node->data;
}

LTree *InitLinkTree()
{
    LTree *tree = (LTree*)malloc(sizeof(LTree));
    if(tree == NULL)
    {
        printf("malloc error!\n");
        return NULL;
    }
    tree->root = CreateTreeNode(NULL);
    return tree;
}

void ClearLinkTree(void *tree)
{
    if(tree == NULL)
        return;
    LTree *tp = (LTree*)tree;
    FreeTreeNode(tp->root);
    free(tp);
}

TNode *GetTreeRoot(LTree *tree)
{
    return tree->root;
}

void ConnectBranch(TNode *parent, TNode *child)
{
    if(parent == NULL || child ==NULL)
        return;
    
    child->parent = parent;
    InsertDLlistTail(&parent->childs,child);
}

bool IsNodeEqual(void *ptr1, void *ptr2)
{
    TNode *node1 = (TNode*)ptr1;
    TNode *node2 = (TNode*)ptr2;
    return node1 == node2;
}

void DisconnectBranch(TNode *parent, TNode *child)
{
    if(parent == NULL && child == NULL)
        return;

    if(child->parent != parent)
    {
        printf("两个节点不是父子关系！\n");
        return;
    }
    child->parent == NULL;
    RemoveByElement(&parent->childs,child,IsNodeEqual,NULL);
}

void TravelTreeNode(TNode *node, int deepth, void (*funcPtr)(void*))
{
    if(node == NULL || funcPtr == NULL)
        return;

    //将根节点排除
    if(node->parent != NULL)
    {
        for(int i = 0; i < deepth; i++)
            printf("    ");
        if(deepth >= 1)
        printf("|____");
        funcPtr(node->data);
    }
    
    DLNode *travelPoint = node->childs.head;
    while(travelPoint->next != NULL)
    {
        TravelTreeNode((TNode *)travelPoint->next->data,deepth+1,funcPtr);
        travelPoint = travelPoint->next;
    }
}

void TravelTree(LTree *tree, void (*funcPtr)(void *))
{
    TravelTreeNode(tree->root,-1,funcPtr);
}


TNode *FindTreeNode(TNode *node, void *value, bool (*funcPtr)(void *, void *))
{
    if(node == NULL || funcPtr == NULL)
        return NULL;
    
    if(node->parent != NULL && funcPtr(node->data,value) == true)
        return node;
    
    TNode *targetNode = NULL;
    DLNode *travelPoint = node->childs.head;
    while(travelPoint->next != NULL)
    {
        targetNode = FindTreeNode((TNode *)travelPoint->next->data,value,funcPtr);
        if(targetNode != NULL)
            return targetNode;
        travelPoint = travelPoint->next;
    }
    return targetNode;
}

TNode *FindLinkTreeNode(LTree *tree, void *value, bool (*funcPtr)(void *, void *))
{
    return FindTreeNode(tree->root,value,funcPtr);
}

void FindAllLF(TNode *node, DLlist *list)
{
    if(node == NULL)
        return;
    
    if(node->childs.len == 0)
    {
        InsertDLlistTail(list, node);
        return;
    }

    DLNode *travelPoint = node->childs.head;
    while(travelPoint->next != NULL)
    {
        FindAllLF((TNode*)travelPoint->next->data,list);
        travelPoint = travelPoint->next;
    }

}
DLlist FindAllLeavesBranches(LTree *tree)
{
    DLlist list;
    InitDLlist(&list);
    FindAllLF(tree->root,&list);
    return list;
}

int GetNodeHeight(TNode *node)
{
    if(node == NULL)
        return 0;

        int height = 0;
        DLNode *travelPoint = node->childs.head;
        while(travelPoint->next != NULL)
        {
            int childHeight = GetNodeHeight((TNode *)travelPoint->next->data);

            height = height > childHeight ? height : childHeight;
            travelPoint = travelPoint->next;
        }
        return height + 1;
}

int GetTreeHeight(LTree *tree)
{
    return GetNodeHeight(tree->root);
}
